home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1997 May / EnigmA AMIGA RUN 18 (1997)(G.R. Edizioni)(IT)[!][issue 1997-05][EAR-CD II].iso / listati / labirinto.c
C/C++ Source or Header  |  1984-10-30  |  2KB  |  123 lines
  1. /* Labirinto.c */
  2. /* Programma per l'analisi del percorso in un labirinto */
  3.  
  4. #include <stdio.h>
  5.  
  6. #define MAXLABX 20
  7. #define MAXLABY 15
  8. int Lab[MAXLABX][MAXLABY];
  9.  
  10. void InitLab(void);
  11. void CopiaLab(int LabS[MAXLABX][MAXLABY], int LabD[MAXLABX][MAXLABY]);
  12. void Passo(int x, int y);
  13. void Percorri(int x, int y);
  14. void DisegnaLab(int L[MAXLABX][MAXLABY]);
  15.  
  16. char *Labirinto[] =
  17. {
  18.   "11111111111111111101",
  19.   "10000000000010000001",
  20.   "11111111101010111111",
  21.   "10100000101010100101",
  22.   "10101110101010110101",
  23.   "10101010101010100101",
  24.   "10100010101010110101",
  25.   "10111110101000000101",
  26.   "10000000001111110101",
  27.   "11101111110000000101",
  28.   "10001010110111110101",
  29.   "10100000010000010101",
  30.   "10111111111111111101",
  31.   "10000000000000000001",
  32.   "11111111111111111111",
  33. };
  34.  
  35. int xs = 1, ys = 13;
  36.  
  37. void InitLab()
  38. {
  39.   char *l;
  40.   int x, y;
  41.  
  42.   for (y=0; y<MAXLABY; y++)
  43.   {
  44.     l = Labirinto[y];
  45.     for (x=0; x<MAXLABX; x++)
  46.       Lab[x][y] = l[x]-'0';
  47.   }
  48.  
  49.   return;
  50. }
  51.  
  52. void CopiaLab(int LabS[MAXLABX][MAXLABY], int LabD[MAXLABX][MAXLABY])
  53. {
  54.   int x, y;
  55.  
  56.   for (y=0; y<MAXLABY; y++)
  57.     for (x=0; x<MAXLABX; x++)
  58.       LabD[x][y] = LabS[x][y];
  59.  
  60.   return;
  61. }
  62.  
  63. int LabM[MAXLABX][MAXLABY];
  64. int LunC, LunM;
  65.  
  66. void Passo(int x, int y)
  67. {
  68.   Lab[x][y] = 2; LunC++;
  69.   if (x == 0 || x == MAXLABX-1 || y == 0 || y == MAXLABY-1)
  70.   {
  71.     if (LunC < LunM)
  72.     {
  73.       CopiaLab(Lab,LabM);
  74.       LunM = LunC;
  75.     }
  76.   }
  77.   else
  78.   {
  79.     if (Lab[x+1][y] == 0) Passo(x+1,y);
  80.     if (Lab[x][y+1] == 0) Passo(x,y+1);
  81.     if (Lab[x-1][y] == 0) Passo(x-1,y);
  82.     if (Lab[x][y-1] == 0) Passo(x,y-1);
  83.   }
  84.   Lab[x][y] = 0; LunC--;
  85.  
  86.   return;
  87. }
  88.  
  89. void Percorri(int x, int y)
  90. {
  91.   LunC = 0;
  92.   CopiaLab(Lab, LabM);
  93.   LunM = MAXLABX*MAXLABY+1;
  94.   Passo(x,y);
  95. }
  96.  
  97. void DisegnaLab(int L[MAXLABX][MAXLABY])
  98. {
  99.   int x, y;
  100.  
  101.   for (y=0; y<MAXLABY; y++)
  102.   {
  103.     for (x=0; x<MAXLABX; x++)
  104.     {
  105.       if (L[x][y] == 1) printf("#");
  106.       else if (L[x][y] == 2) printf("+");
  107.       else printf(" ");
  108.     }
  109.     printf("\n");
  110.   }
  111. }
  112.  
  113. int main()
  114. {
  115.   InitLab();
  116.   printf("Questo è il labirinto:\n");
  117.   DisegnaLab(Lab);
  118.   Percorri(xs,ys);
  119.   printf("\nEcco il percorso minimo dal punto di partenza (%d,%d) all'uscita:\n",xs,ys);
  120.   DisegnaLab(LabM);
  121.   printf("Lunghezza del percorso: %d\n",LunM);
  122. }
  123.